#include <iostream>
using namespace std;
#include<ctime>
#include<vector>
#include<unordered_map>

#if 0

/************************* 数论 **********************/
// 补：C++修正取余：n % k => (n % k + k) % k
/***************** 一、质数 **************/
// 在大于1的整数中，如果其约数只有1和它本身，就被称为质数(或素数)。

// 1、质数的判定-试除法 O(sqrt(n)) 性质：所有数的约数都是成对出现的，我们可以只枚举每对当中较小的那个。枚举到sqrt(n)
bool is_prime(int n)
{
    if (n <= 1) return false;

    // for循环的判断条件有很多写法: i <= sqrt(n); i*i <= n; i <= n/i; 第一个效率低，第二个可能会出现溢出，推荐第三个
    for (int i = 2; i <= n / i; ++i)
        if (n % i == 0) return false;
    return true;
}

// 2、分解质因数 O(logn ~ sqrt(n))。n = p1^k1 * p2^k2 * p3^k3 * ...  (p1 < p2 < p3 < ..., 其中p1、p2...都是质数)
void divide(int n)
{
    // //O(n)
    // for(int i = 2; i <= n; ++i)
    // {
    //     if(n % i == 0)
    //     {
    //         int cnt = 0; // cnt计算当前i的指数
    //         while(n % i == 0)
    //         {
    //             n /= i;
    //             ++cnt;
    //         }
    //         printf("%d %d\n", i, cnt);
    //     }
    // }

    // 性质：n最多只包含1个大于sqrt(n)的质因子
    for (int i = 2; i <= n / i; ++i)
    {
        if (n % i == 0)
        {
            int cnt = 0;
            while (n % i == 0)
            {
                ++cnt;
                n /= i;
            }
            printf("%d %d\n", i, cnt);
        }
    }
    if (n > 1)
        printf("%d %d\n", n, 1);
}

// 3、筛质数
const int N = 1e8 + 10;
int pri[N], idx;
bool st[N];

void prime(int n) // 1~n所有的质数
{
    // // 朴素筛 (调和级数极限是ln(n) + C, O(nlogn))
    // // 枚举所有数，没被筛过就放入pri数组。然后把每次枚举的数的倍数筛掉
    // for (int i = 2; i <= n; ++i)
    // {
    //     // i没被筛过，说明是质数。放入pri数组，再把它的倍数删掉
    //     // 因为是从小到大枚举的，i没被筛，说明2 ~ i-1中的任何一个数都不能筛掉i，即2 ~ i-1中的所有数都不是i的约数，所以i是质数
    //     if (!st[i])
    //         pri[idx++] = i;
    //     for (int j = i + i; j <= n; j += i)
    //         st[j] = true;
    // }

    // // 埃氏筛 O(nlog(logn)), 质数定理：1 ~ n中有 n / lnn 个质数
    // // 枚举所有数，没被筛过就放入pri数组。只需把每次枚举的 质数 的倍数筛掉
    // for(int i = 2; i <= n; ++i)
    // {
    //     // i没被筛，说明2 ~ i-1中的任何一个 质数 都不能筛掉i。
    //     // 而任何一个数n，都有：n = p1^k1 * p2^k2 * p3^k3 * ... * pm^km (p1 < p2 < p3 < ... < pm <= n, 其中p1、p2...、pm都是质数) 注：最大的质数pm <= n
    //     if(!st[i])
    //     {
    //         pri[idx++] = i;
    //         for (int j = i + i; j <= n; j += i)
    //             st[j] = true;
    //     }
    // }

    // 线性筛 O(n), n只会被最小质因子筛掉  ---> 1亿个数据筛选只需不到1s
    // 枚举所有数，并删除pri[j] * i
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
            pri[idx++] = i;
        // for循环的判断条件：j < idx && pri[j] * i <= n; 可以不要j < idx, 因为if那里会break。
        // 1、i是合数，那一定存在最小质因数pri[j], i % pri[j] == 0 ---> break;
        // 2、i是质数，由于pri[idx++] = i; 那一定会在枚举到最后一个质数时break
        for (int j = 0; pri[j] <= n / i; ++j)
        {
            st[pri[j] * i] = true;
            if (i % pri[j] == 0) break;
            // 走到if成立时，由于是从小到大枚举的，pri[j]一定是i的最小质因子，所以pri[j] 叶一定是 pri[j] * i 的最小质因子
            // i % pri[j] != 0时，pri[j] 一定小于i的最小质因子，所以pri[j] 也一定是 pri[j]*i 的最小质因子
        }
        // 如何做到每个合数都会被筛掉？
        // 对于任意一个合数x，一定存在最小质因子pj, 那在枚举到 x/pj时，x就会被筛掉
    }
}

//测试线性筛
void test_liner(int n)
{
    int b = clock();
    vector<int> pri;
    pri.reserve(n / 10);
    vector<bool> st(n + 1, false);
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
            pri.push_back(i);
        for (int j = 0; pri[j] <= n / i; ++j)
        {
            st[pri[j] * i] = true;
            if (i % pri[j] == 0)
                break;
        }
    }
    int e = clock();
    printf("个数：%d, 用时:%d\n", pri.size(), e - b);
}

/*********************** 约数 *********************/
// 一个数n，有多少个约数？logn左右
// 从整体卡：1, 2, ..., n 所有数中的约数跟倍数相同，n + n/2 + n/3 + ... + n/n = nlogn ===>平均下来看，每个数就有logn个约数
// 1、试除法求约数 O(sqrt(n)), int类型的所有数中约数个数最大的那个数的约数 大约有1500个
void get_divisors(int x)
{
    const int N = 1600;
    int div[N], l = 0, r = N - 1; // [0, l) 跟 (r, N) 存放的是约数

    for(int i = 1; i <= x / i; ++i)
    {
        if(x % i == 0) 
        {
            div[l++] = i;
            div[r--] = x / i;
        }
    }

    int i = 0;
    for(; i < l; ++i) printf("%d ", div[i]);

    i = r + 1;
    // div[i] * div[i] == x, 会放两个重复值
    if(div[i] * div[i] == x) ++i;
    for(; i < N; ++i)  printf("%d ", div[i]);
    puts("");
}

// n = p1^a1 * p2^a2 * p3^ a3 * ... pk^ak
// 2、约数个数 = (a1 + 1)(a2 + 1)...(ak + 1) --->分解质因数，相乘
int div_cnt(int n)
{
    int ans = 1;
    for(int i = 2; i <= n / i; ++i)
    {
        if(n % i == 0)
        {
            int c = 0;
            while(n / i == 0)
            {
                ++c;
                n /= i;
            }
            ans *= c + 1;
        }
    }
    if(n > 1)
        ans *= 2;
    return ans;
}

// n = p1^a1 * p2^a2 * p3^ a3 * ... pk^ak
// 3、约数之和 = (p1^0 + p1^1 + ... + p1^a1)(p2^0 + p2^1 +...+ p2^a2)...
// https://www.acwing.com/problem/content/description/873/

// 分解质因数，放入哈希表
/*
unordered_map<int, long long> ha;
void divisor(int n)
{
    for (int i = 2; i <= n / i; ++i)
    {
        if (n % i == 0)
        {
            int c = 0;
            while (n % i == 0)
            {
                ++c;
                n /= i;
            }
            ha[i] += c;
        }
    }
    if (n > 1)
        ha[n]++;
}
int main()
{
    int n, a;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d", &a);
        divisor(a);
    }
    long long ans = 1, mod = 1e9 + 7;
    for (auto &[p, k] : ha) //p: 底数，k: 指数
    {
        //求 p^0 + p^1 + ... p^k
        long long sum = 0, t = 1;
        for (int i = 0; i <= k; ++i)
        {
            sum = (sum + t) % mod;
            t = (t * p) % mod;
        }
        ans = (ans % mod) * (sum % mod) % mod;

        // // p^0 + p^1 + ... p^k = 1 + p (p^0 + p^1 + ... + p^k-1); ==> 当前状态 = 上一个状态 * p + 1;
        // long long sum = 1;
        // while(k--)
        //     t = (t * p + 1) % mod;
        // ans = (ans % mod) * (sum % mod) % mod;
    }
    printf("%lld", ans);
    return 0;
}*/

// 4、最大公约数-辗转相除法 O(logn) 原理：(a, b) = (b, a % b)
// d|x, d|y => d|ax+by
// 充分性：d|a, d|b, 而a % b = a - c*b ==> d|a-c*b
// 必要性：d|b, d|a%b 即 d|a - c*b ==> d|a - c*b + c*b
// 注：gcd(a, 0) = 0, 任何数都能整除0
int gcd(int a, int b)
{
    if(a % b == 0)
        return b;
    return gcd(b, a % b);
    // return b == 0 ? a : gcd(a, b);
}

#endif
/*思考：
如何快速求出 p^0 + p^1 + ... + p^n
分治

*/